package com.yun.algorithm.divideandconquer;

import java.util.concurrent.ThreadLocalRandom;

/**
 * 快速排序
 * 分治
 */
public class QuickSelect {

    public static void main(String[] args) {
        int[] array = {6, 5, 1, 2, 4};
        System.out.println(quick(array,0,array.length-1,0));
    }

    static int quick(int[] array, int left, int right, int i) {
        int p = partition(array, left, right);//基准点元素索引值
        if (p == i) {
            return array[p];
        } else if (i < p) {
            return quick(array,left,p-1,i);
        }else {
            return quick(array,p+1,right,i);
        }
    }

    static int partition(int[] a, int left, int right) {
        int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
        swap(a, idx, left);
        int pv = a[left];//基准点元素值
        int i = left;
        int j = right;
        while (i < j) {
            //1.j从右向左找小的
            while (i < j && a[j] > pv) {
                j--;
            }
            //2.i从左向右找大的
            while (i < j && a[i] <= pv) {
                i++;
            }
            swap(a, i, j);
        }
        swap(a, left, i);
        return i;
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

}
